package arithmetic2;

import org.apache.log4j.Logger;

/**
 * @author Ajie
 * @date 2021/12/30
 * @function 大数据压缩 bit - map ,bitmap
 * https://www.cnblogs.com/mingweiyard/p/10025348.html
 * <p>
 * bitmap海量数据的快速查找和去重
 * 题目描述
 * 给你一个文件，里面包含40亿个整数，写一个算法找出该文件中不包含的一个整数， 假设你有1GB内存可用。
 * 40亿int 大小：4*10^10*4 byte == 15258 MB = 14 GB
 * <p>
 * 如果你只有10MB的内存呢？
 * 分块处理
 * <p>
 *
 * 解题思路：
 * bitmap基本思想是一位表示一个整数。
 * eg: 1个 int 4byte 32位 32bit ,可以表示32个数字是否存在
 * 1 bit :0 不存在  1存在
 * 2 bit :00 不存在 1存在 11重复。（其他情况，扩展）
 * 所以数据存储效率，高了 32倍，1个int 表示 32 个int。
 * 算法，换空间。
 * 40亿 15258 MB /32 = 476 MB
 * <p>
 * <p>
 * 实现细节
 * 首先我们用int来表示：int bmap[1+N/32]; //N是总数，N=40亿，一个int32bit
 * 然后我们插入一个整数val，要先计算val位于数组bmap中的索引:index = val/32;
 * <p>
 * 比如整数33，index=33/32=1,第33位于数组中的index=1
 * 比如整数67，index=67/32=2,位于数组中index=2
 * <p>
 * 然后在计算在这个index中的位置，因为数组中的每个元素有32位
 * 33，index=1，在1中的位置为33%32=1
 * 67，index=2，在2中的位置为67%32=3
 * <p>
 * 存储：
 * 然后就是标识这个位置为1：
 * bmap[val/32] |= (1<<(val%32));
 * 33: bmap[1] != (1<<1);//xxxxxx 1 x,红丝位置被置为1 //TODO 这个更快？
 * 67: bmap[2] != (1<<3);//xxxx 1 xxx
 * <p>
 * <p>
 * 怎样检测整数是否存在？
 * 比如我们检测33，同样我们需要计算index，以及在index元素中的位置
 * 33: index = 1, 在bmap[1]中的位置为 1，只需要检测这个位置是否为1
 * int target = 1 << (val % BitLen);
 * return ( bmap[val / BitLen] & target ) == target;
 *
 * <p>
 * bool testVal(int val)
 * {
 *         int target = 1 << (val % BitLen);
 *         return ( bmap[val / BitLen] & target ) == target;
 * }
 */
public class Arith_BitMap {
    private static final Logger logger = Logger.getLogger(Arith_BitMap.class);

    public static void main(String[] args) {
        logger.info("main:(7&2): "+(7&2));

        Arith_BitMap arith_bitMap = new Arith_BitMap();
        int[] a = {1, 2, 3, 4, 6, 7};

        for (int i = 0; i < 6; ++i) {
            arith_bitMap.setVal(a[i]);
        }

        logger.info("main: hasVal:"+arith_bitMap.hasVal(1));
        logger.info("main: hasVal:"+arith_bitMap.hasVal(5));
    }

    int N = 4* 1000 * 1000;//MaxN int 总数量
    //    int N = 4_000_000_000;//MaxN
    int BitLen = 32;//长度 32，压缩32倍。
    int[] bmap = new int[1 + N / BitLen];//缓存数组

    void setVal(int val) {
        bmap[val / BitLen] |= (1 << (val % BitLen));// 左移 对应位置，然后 | 。
    }

    /**
     * main:(7&2): "+(7&2))=2
     * 111 & 10 = 10
     * @param val
     * @return
     */
    boolean hasVal(int val) {
        int target = 1 << (val % BitLen);// 左移 对应位置,然后拿到那个位置的值。
        return ( bmap[val / BitLen] & target ) == target;//拿到 index & 对应位置 == 对应位置的值。
    }

}
